Garbage collection is the automatic management of dynamically allocated memory storage. Garbage collection typically involves an automatic periodic reclamation of dynamically allocated memory by a garbage collector, i.e., the process performing the garbage collection. Various events may trigger garbage collection, for example, garbage collection may be triggered during a memory allocation step where the amount of unallocated memory is less than some threshold value. In most implementations of garbage collection, the executing program is suspended while garbage collection takes place. Once the garbage collection has been completed, the executing program is allowed to resume.
To reclaim a dynamically allocated piece of memory, the garbage collector ensures that the piece of memory to be reclaimed is not live. The term “live” in the context of garbage collection refers to a piece of memory containing data that is required by an executing program, or is at least reachable by following a path of pointers from a root, i.e., a memory location that is always deemed as live. There are many algorithms that have been developed to solve this problem. One such algorithm is the Mark-Sweep Algorithm, see “John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Communications of the ACM, 3:184-195, 1960.” The Mark-Sweep algorithm is performed in two phases. The first phase is the marking phase. In the first phase, the algorithm performs a global traversal of a heap, i.e., an area of memory used for dynamic memory allocation where blocks of memory are allocated and freed in an arbitrary order and the pattern of allocation and size of blocks is not known until run time, to determine which parts of the heap are available for reclamation. In an exemplary computer system, the heap may be located in a portion of memory, with an L1 cache and an L2 cache. A number of methods have been developed to perform this traversal. One such method is a recursive traversal of the heap. In a recursive traversal of the heap, the algorithm starts at a root and proceeds to follow all pointers connected directly and indirectly to the roots, such that all pieces of memory connected directly or indirectly to the root are found. Every piece of memory encountered in the recursive traversal is marked as live. Upon completion of the mark phase, the second phase (denoted the sweep phase) is initiated. During the sweep phase, any piece of memory that is not marked as live is reclaimed.
FIG. 1 illustrates a heap after completion of the marking phase in accordance with the Mark-Sweep algorithm described above. The heap (2) contains seven dynamically allocated pieces of memory, each denoted as a cell. Cell (4) is referenced by a root reference (3) and is marked as live, as denoted by the associated shaded mark bit (18). As described above, during the marking phase the Mark-Sweep algorithm recursively traces all pointers from the root cell (4) and marks all cells encountered as live. In this particular example, cell (6), cell (8) and cell (12) are all marked as live, as denoted by the shaded reference bit on each of the aforementioned cells. Cell (10), cell (14), and cell (16) are not referenced, directly or indirectly, by the root cell (4) and, as such, are not marked as live. Once the marking phase is complete, all cells that are not marked as live are reclaimed, during the sweep phase. In this example, cell (10), cell (14), and cell (16) would be reclaimed during the sweep phase.
While the garbage collection algorithm illustrated above collects garbage over the entire heap, only collecting garbage in a subset of the heap is often desirable. For example, in-cache garbage collection only collects dynamically allocated objects within the cache. This approach increases the garbage collection efficiency as there is no garbage collection performed in memory external to the cache. In addition, as object-based systems become widespread, large object stores are becoming more common. To date, most solutions have been implemented using stock hardware, and supporting software. While acceptable as an initial solution, large performance gains may be possible using architectures more suited to the task at hand.